//https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=295&tqId=2294660&ru=/exam/intelligent&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fintelligent%3FdayCountBigMember%3D%25E8%25BF%259E%25E7%25BB%25AD%25E5%258C%2585%25E6%259C%2588%26questionJobId%3D10%26tagId%3D21003%26type%3Dvip
//编辑距离
//给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
//你可以对字符串进行3种操作：
//1.插入一个字符
//2.删除一个字符
//3.修改一个字符。
//字符串长度满足1 <= n <= 1000保证字符串中只出现小写英文字母。

int Min(int a, int b)
{
    return a > b ? b : a;
}

int editDistance(char* str1, char* str2 ) {
    // write code here
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int dp[len1 + 1][len2 + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= len1; i++)
    {
        dp[i][0] = i;
    }
    for(int j = 0; j <= len2; j++)
    {
        dp[0][j] = j;
    }
    for(int i = 0; i < len1; i++)
    {
        for(int j = 0; j < len2; j++)
        {
            if(str1[i] == str2[j])
            dp[i + 1][j + 1] = dp[i][j];
            else
            {
                dp[i + 1][j + 1] = Min(dp[i][j], Min(dp[i][j + 1], dp[i + 1][j])) + 1;
                //在dp[i][j]的基础上修改
                //在dp[i][j+1]或dp[i+1][j]的基础上增加或减少
            }
        }
    }
    return dp[len1][len2];
}